Trampolined Style

再帰をloopに変換することで、Stack Over Flowを防ぐ1つの手段

runtimeで末尾再帰の最適化をemulateしている

概要

言語仕様として末尾再帰の最適化がない言語では、再帰の数が増えすぎるとStack Over Flowを起こす

そこで、Trampoline関数なるものを利用し、一工夫加えることでloopに変換させることができる

例

Stack Over Flowする例

code:js

const countDown = (num) => {

console.log(num);

if (num === 1) return 1;

return countDown(num - 1);

};

countDown(30000);

wandboxで実行したら17500あたりまでログを吐いた後にMaximum call stack size exceededが起きた

Trampoline関数を用意して微修正する

code:js

const countDown = (num) => {

console.log(num);

if (num === 1) return 1;

return () => countDown(num - 1); // 関数を返すように修正

}

// trampoline function

const trampoline = fn => (...args) => {

let result = fn(...args)

while (typeof result === 'function') {

result = result()

}

return result

}

const tramped = trampoline(countDown);

console.log(tramped(30000)); //耐える

countDownは、

終了条件では値を返す

それ以外は、再帰しつつ「関数」を返す

trampolineは関数を返す

「fnをloop構造に変換した関数」を返す

ここでは、その関数をtrampedと呼ぼうmrsekut.icon

tramped自体は1回しか呼ばれていない

再帰の回数だけwhileが回っている

再帰の終了条件となる結果が、最後のresultに入ってそれが返ってくる

全く同じ挙動をするのに、スタックを全く積まないのでoverflowしない

速度的には、trampolineを使わずにcountDownを手動でloopに書き直したほうが速い

それはそうmrsekut.icon

countDownは、再帰の回数だけ関数呼び出しすることになることには変わりない

JSはこの説明に良い例だが、実際JSで再帰書くことはほぼないだろうmrsekut.icon

概念の理解の助けになる

末尾再帰の最適化がされない言語の例

e.g. Python, C#, JavaScript

PureScriptは基本は最適化されるが条件が重なるとされない場合がある

例えば上記のようなcountDownを実装し、logを仕込むとstack over flowする

この条件の真意は理解できてない #??

TrampolineモナドやFreeモナドなどを使えば回避できる

ちなみにJSの場合は、

最近のBabelを使えばちゃんと末尾再帰の最適化が施されるので問題ない ref

どの辺が「トランポリン」なのか？

この解答のvisualizeがわかりやすい

最適化なしの再帰呼び出しの場合、

最後までstackが積み上げられたあと、popされていくので、

時間を横軸、stackを縦軸に絵を描くと、ピラミッド型になる

一方で、loopで関数呼び出しするようにすれば、

loopのたびごとに、1push、1popが行われる

同様に絵を描くと、stack上でぴょんぴょんしてる感じになる

この感じが「トランポリン」なのらしい